//===--- ClusteredBitVector.h - A size-optimized bit vector -----*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file defines the ClusteredBitVector class, a bitset data
// structure.
//
// For example, this would be reasonable to use to describe the
// unoccupied bits in a memory layout.
//
// Primary mutators:
//   - appending another vector to this vector
//   - appending a constant vector (<0,0,...,0> or <1,1,...,1>) to this vector
//
// Primary observers:
//   - testing a specific bit
//   - converting to llvm::APInt
//
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_BASIC_CLUSTEREDBITVECTOR_H
#define POLARPHP_BASIC_CLUSTEREDBITVECTOR_H

#include "llvm/ADT/APInt.h"
#include "llvm/ADT/Optional.h"
#include "polarphp/basic/Debug.h"
#include <cassert>

namespace polar {

/// A vector of bits.
class ClusteredBitVector {
   using APInt = llvm::APInt;

   /// Represents the bit vector as an integer.
   /// The least-significant bit of the integer corresponds to the bit
   /// at index 0. If the optional does not have a value then the bit
   /// vector has a length of 0 bits.
   llvm::Optional<APInt> Bits;

   /// Copy constructor from APInt.
   ClusteredBitVector(const APInt &bits) : Bits(bits) {}

   /// Move constructor from APInt.
   ClusteredBitVector(APInt &&bits) : Bits(std::move(bits)) {}
public:
   /// Create a new bit vector of zero length.  This does not perform
   /// any allocations.
   ClusteredBitVector() = default;

   ClusteredBitVector(const ClusteredBitVector &other)
      : Bits(other.Bits) {}

   ClusteredBitVector(ClusteredBitVector &&other)
      : Bits(std::move(other.Bits)) {}

   /// Create a new ClusteredBitVector from the provided APInt,
   /// with a size of 0 if the optional does not have a value.
   ClusteredBitVector(const llvm::Optional<APInt> &bits)
      : Bits(bits) {}

   /// Create a new ClusteredBitVector from the provided APInt,
   /// with a size of 0 if the optional does not have a value.
   ClusteredBitVector(llvm::Optional<APInt> &&bits)
      : Bits(std::move(bits)) {}

   ClusteredBitVector &operator=(const ClusteredBitVector &other) {
      this->Bits = other.Bits;
      return *this;
   }

   ClusteredBitVector &operator=(ClusteredBitVector &&other) {
      this->Bits = std::move(other.Bits);
      return *this;
   }

   ~ClusteredBitVector() = default;

   /// Return true if this vector is zero-length (*not* if it does not
   /// contain any set bits).
   bool empty() const {
      return !Bits.hasValue();
   }

   /// Return the length of this bit-vector.
   size_t size() const {
      return Bits ? Bits.getValue().getBitWidth() : 0;
   }

   /// Append the bits from the given vector to this one.
   void append(const ClusteredBitVector &other) {
      // Nothing to do if the other vector is empty.
      if (!other.Bits) {
         return;
      }
      if (!Bits) {
         Bits = other.Bits;
         return;
      }
      APInt &v = Bits.getValue();
      unsigned w = v.getBitWidth();
      v = v.zext(w + other.Bits.getValue().getBitWidth());
      v.insertBits(other.Bits.getValue(), w);
      return;
   }

   /// Add the low N bits from the given value to the vector.
   void add(size_t numBits, uint64_t value) {
      append(fromAPInt(APInt(numBits, value)));
   }

   /// Append a number of clear bits to this vector.
   void appendClearBits(size_t numBits) {
      if (numBits == 0) {
         return;
      }
      if (Bits) {
         APInt &v = Bits.getValue();
         v = v.zext(v.getBitWidth() + numBits);
         return;
      }
      Bits = APInt::getNullValue(numBits);
   }

   /// Extend the vector out to the given length with clear bits.
   void extendWithClearBits(size_t newSize) {
      assert(newSize >= size());
      appendClearBits(newSize - size());
   }

   /// Append a number of set bits to this vector.
   void appendSetBits(size_t numBits) {
      if (numBits == 0) {
         return;
      }
      if (Bits) {
         APInt &v = Bits.getValue();
         unsigned w = v.getBitWidth();
         v = v.zext(w + numBits);
         v.setBitsFrom(w);
         return;
      }
      Bits = APInt::getAllOnesValue(numBits);
      return;
   }

   /// Extend the vector out to the given length with set bits.
   void extendWithSetBits(size_t newSize) {
      assert(newSize >= size());
      appendSetBits(newSize - size());
   }

   /// Test whether a particular bit is set.
   bool operator[](size_t i) const {
      assert(i < size());
      return Bits.getValue()[i];
   }

   /// Intersect a bit-vector of the same size into this vector.
   ClusteredBitVector &operator&=(const ClusteredBitVector &other) {
      assert(size() == other.size());
      if (Bits) {
         APInt &v = Bits.getValue();
         v &= other.Bits.getValue();
      }
      return *this;
   }

   /// Union a bit-vector of the same size into this vector.
   ClusteredBitVector &operator|=(const ClusteredBitVector &other) {
      assert(size() == other.size());
      if (Bits) {
         APInt &v = Bits.getValue();
         v |= other.Bits.getValue();
      }
      return *this;
   }

   /// Set bit i.
   void setBit(size_t i) {
      assert(i < size());
      Bits.getValue().setBit(i);
   }

   /// Clear bit i.
   void clearBit(size_t i) {
      assert(i < size());
      Bits.getValue().clearBit(i);
   }

   /// Toggle bit i.
   void flipBit(size_t i) {
      assert(i < size());
      Bits.getValue().flipBit(i);
   }

   /// Toggle all the bits in this vector.
   void flipAll() {
      if (Bits) {
         Bits.getValue().flipAllBits();
      }
   }

   /// Set the length of this vector to zero.
   void clear() {
      Bits.reset();
   }

   /// Count the number of set bits in this vector.
   size_t count() const {
      return Bits ? Bits.getValue().countPopulation() : 0;
   }

   /// Determine if there are any bits set in this vector.
   bool any() const {
      return Bits && Bits.getValue() != 0;
   }

   /// Determine if there are no bits set in this vector.
   ///
   /// \return \c !any()
   bool none() const {
      return !any();
   }

   friend bool operator==(const ClusteredBitVector &lhs,
                          const ClusteredBitVector &rhs) {
      if (lhs.size() != rhs.size()) {
         return false;
      }
      if (lhs.size() == 0) {
         return true;
      }
      return lhs.Bits.getValue() == rhs.Bits.getValue();
   }
   friend bool operator!=(const ClusteredBitVector &lhs,
                          const ClusteredBitVector &rhs) {
      return !(lhs == rhs);
   }

   /// Return this bit-vector as an APInt, with low indices becoming
   /// the least significant bits of the number.
   APInt asAPInt() const {
      // Return 1-bit wide zero APInt for a 0-bit vector.
      return Bits ? Bits.getValue() : APInt();
   }

   /// Construct a bit-vector from an APInt.
   static ClusteredBitVector fromAPInt(const APInt &value) {
      return ClusteredBitVector(value);
   }

   /// Construct a bit-vector from an APInt.
   static ClusteredBitVector fromAPInt(APInt &&value) {
      return ClusteredBitVector(std::move(value));
   }

   /// Return a constant bit-vector of the given size.
   static ClusteredBitVector getConstant(size_t numBits, bool value) {
      if (numBits == 0) {
         return ClusteredBitVector();
      }
      auto vec = APInt::getNullValue(numBits);
      if (value) {
         vec.flipAllBits();
      }
      return ClusteredBitVector(vec);
   }

   /// Pretty-print the vector.
   void print(llvm::raw_ostream &out) const;
   POLAR_DEBUG_DUMP;
};

} // end namespace polar

#endif // POLARPHP_BASIC_CLUSTEREDBITVECTOR_H
